/**
 * Created by L.jp
 * Description:在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。
 * 并将P对1000000007取模的结果输出。 即输出P mod 1000000007
 * User: 86189
 * Date: 2022-05-26
 * Time: 9:15
 */
//要求：空间复杂度 O(n)，时间复杂度 O(nlogn)
public class Solution {
    //引入去全局变量
    private static long count=0;
    public static int InversePairs(int [] array) {
//        int count=0;
//        //暴力解法    超出时间限制，时间复杂度：O(n^2)
//        for(int i=0;i<array.length-1;i++){   //i表示前面的数，最多到倒数第二个数
//            for(int j=i+1;j<array.length;j++){  //j表示后面的数，最多到数组最后一个数
//                if(array[i]>array[j]){
//                    count++;
//                }
//            }
//        }
//        return count % 1000000007;
    
    
        /*逆序对，要求前面的数必须大于后面的数，找整个数组的逆序对，我们可以划分为子问题，找某一个区间的逆序对
        * 针对于暴力解法的优化，我们可以不用遍历数组n^2次，我们可以把数组先划分成两个有序的子数组
        * 然后再合并这两个子数组成一个数组，再合并的过程中那不就是涉及到两个元素一前一后的比较吗
        * 只要后半部分数组的第一个元素小于前半部分数组的第一个元素，那么因为数组已经各自有序
        * 所以前半部分数组的全部元素肯定和后半部分数组的第一个元素构成逆序对，个数直接只用下标相减即可
        * 这样就减少了计算的成本，每一次合并的时候都可以这样计算逆序对的个数，这就利用到了归并排序的思想
        * 计算逆序对的个数发生在合并两个子数组的时候*/
        //空间复杂度 O(n)，时间复杂度 O(nlogn)
        //归并排序核心思想是分治思想，分就是使用二分法划分数组，直到两个数组各自只有一个元素，治就是把划分的数组之间使用归并排序合并成一个新的数组
        //在合并的时候就是统计逆序对的时候
        int len=array.length;
        divide(array,0,len-1);
        return (int) (count%1000000007) ;  //把结果转化为整型
    }
    //归并排序
    //1.划分区间
    private static void divide(int[] array, int left, int right) {
        //划分到只有一个元素，直接返回去合并
        if(left>=right){
            return;
        }
        int mid=left+(right-left)/2;
        //否则就要继续划分
        //以mid为界限划分左区间数组
        divide(array,left,mid);
        ////以mid为界限划分右区间数组
        divide(array,mid+1,right);
        //返回的时候走到这个代码块，说明此时两个区间的子数组只剩一个元素，可以进行合并
        merge(array,left,mid,right);
    }
    //归并排序
    //2.合并区间数组
    private static void merge(int[] array, int left, int mid,int right) {
        //借助一个新数组合并排序
        int[] tmp=new int[right-left+1];
        //左区间合并的起始下标
        int i=left;
        //右区间合并的起始下标
        int j=mid+1;
        //定义辅助数组的下标
        int index=0;
        //开始合并两个子区间
        while (i<=mid && j<=right){
            if(array[i]<array[j]){
                //前面的小于后面的，说明没有逆序对，直接合并排序到辅助数组里即可
                tmp[index++]=array[i++];
            }else{
                //前面的大于后面的，那么就有逆序对，合并的同时记录逆序对个数
                tmp[index++]=array[j++];
                //这是使用下标统计逆序对的核心代码
                //由于左半部分数组已经有序，如果左边的当前位置都比右边的当前位置大，
                // 那么说明左边当前位置以后的直到左边界限mid的这些元素都比右边当前位置的元素大
                //则构成逆序对，那么左边剩下的元素包括当前元素，统计这些个数使用mid-i+1求得
                count+=mid-i+1;
            }
        }
        //如果遍历完了左边部分或者右边部分，直接另一部分的区间赋值给新数组
        while (i<=mid){
            tmp[index++]=array[i++];
        }
        while (j<=right){
            tmp[index++]=array[j++];
        }
        //合并完之后需要把合并好的数组赋值给原来的数组
        //保证在下一次合并的时候，原数组已经部分有序
        for(int k=0;k<tmp.length;k++){
            array[left+k]=tmp[k];  //left永远是0，只有k在变
        }
        
    }
    
    public static void main(String[] args) {
        int[] nums={1,2,3,4,5,6,7,0};
        System.out.println(InversePairs(nums));
    }
}
